【题解】 [SDOI2011]消耗战 虚树+树形DP luoguP2495 | Qiuly's blog!

【题解】 [SDOI2011]消耗战 虚树+树形DP luoguP2495

Posted on | Edited on | In | Comments:

去 $Mina!$ 上了解了一波虚树，$\%\%\% XZY$ 学长太强辣！

这次总算明白了些虚树，然后 $XZY$ 大佬的例题就是消耗战。

于是看了过来。

首先，考虑普通的树形 $DP$ ，设 $dp[u]$ 表示在 $u$ 为根的子树中满足目标所花费的最小代价 ，那么转移方程也不是很难，我们枚举 $u$ 的孩子 $v$ 。如果 $v$ 本身就是”能源丰富的岛屿”那么 $dp[u]+=G[i].val$ ，其中 $G[i].val$ 表示 $u$ 到 $v$ 的边的边权。为什么这样转移呢？因为 $v$ 必须切断。

那么没有必要切断的岛屿呢？就分切/不切两种情况了：

这个也很好懂。

这个时候我们打完代码交一发发现只有 $40$ 分……往下看，可以看到 $n$ 到最后的顶尖数据有 $250000$ ……

但是我们可以观察到，$\sum k_i \leq 5*10^5$ ，发现总共的 $k$ 也不过这么大，这个时候我们可以用虚树来解决。

$Qiuly$ ：有关虚树的文章先咕一下蛤，最近有点忙。

建好虚树后直接用上面的转移方程做就得了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2.5e5+7;
const int LogN=27;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct graph {
    int head[N],nxt[N<<1],to[N<<1],val[N<<1],cnt;
    void init() {memset(head,-1,sizeof(head));cnt=0;}
    graph() {init();}
    void add(int u,int v,int w) {
        nxt[cnt]=head[u],to[cnt]=v,val[cnt]=w,head[u]=cnt++;
    }
}G;

int n,m,point[N],stack[N],top;
ll dp[N];bool vis[N];

namespace LCA {
    int dep[N],fa[N][LogN+3],num[N][LogN+3];
    int id[N],dfn,Edge_Mx;
    void _Pre_Lca(int u,int f) {
        fa[u][0]=f,dep[u]=dep[f]+1,id[u]=++dfn;
        for(int i=1;i<=LogN;++i) {
            fa[u][i]=fa[fa[u][i-1]][i-1];
            num[u][i]=min(num[u][i-1],num[fa[u][i-1]][i-1]);
        }
        for(int i=G.head[u];~i;i=G.nxt[i]) 
            if(G.to[i]!=f)num[G.to[i]][0]=G.val[i],_Pre_Lca(G.to[i],u);
    }
    int lca(int x,int y) {
        Edge_Mx=inf;
        if(x==y)return x;
        if(dep[x]<dep[y])swap(x,y);
        for(int i=LogN;i>=0;--i)
            if(dep[fa[x][i]]>=dep[y])
                Edge_Mx=min(Edge_Mx,num[x][i]),x=fa[x][i];
        if(x==y)return x;
        for(int i=LogN;i>=0;--i)
            if(fa[x][i]!=fa[y][i])
                Edge_Mx=min(Edge_Mx,min(num[x][i],num[y][i])),
                x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}using namespace LCA;

bool cmp(int x,int y) {return id[x]<id[y];}

void solve(int u) {//DP过程
    dp[u]=0;
    for(int i=G.head[u];~i;i=G.nxt[i]) {
        solve(G.to[i]);
        if(vis[G.to[i]])dp[u]+=G.val[i];
        else dp[u]+=min((ll)G.val[i],dp[G.to[i]]);
    }return;
}

void build(int k) {//建立虚树
    sort(point+1,point+1+k,cmp);
    stack[top=1]=1,G.cnt=0,G.head[1]=-1;
    for(int i=1;i<=k;++i) if(point[i]!=1) {
        int l=lca(stack[top],point[i]);
        if(l!=stack[top]) {
            while(id[l]<id[stack[top-1]]) {
                lca(stack[top-1],stack[top]);
                G.add(stack[top-1],stack[top],Edge_Mx);
                --top;
            }
            if(id[l]>id[stack[top-1]]) {
                G.head[l]=-1,lca(l,stack[top]);
                G.add(l,stack[top],Edge_Mx),stack[top]=l;
            }
            else lca(l,stack[top]),G.add(l,stack[top],Edge_Mx),--top;
        }
        G.head[point[i]]=-1,stack[++top]=point[i];
    }
    for(int i=1;i<top;++i)
        lca(stack[i],stack[i+1]),G.add(stack[i],stack[i+1],Edge_Mx);
}

int main() {
    IN(n);
    for(int i=1;i<n;++i) {
        int u,v,w;IN(u),IN(v),IN(w);
        G.add(u,v,w),G.add(v,u,w);
    }
    _Pre_Lca(1,0),IN(m);
    while(m--) {
        int k;IN(k);
        for(int i=1;i<=k;++i)IN(point[i]),vis[point[i]]=true;
        build(k);
        solve(1),printf("%lld\n",dp[1]);
        for(int i=1;i<=k;++i)vis[point[i]]=false;
    }
    return 0;
}

本文标题:【题解】 [SDOI2011]消耗战 虚树+树形DP luoguP2495

文章作者:Qiuly

发布时间:2019年03月31日 - 00:00

最后更新:2019年05月05日 - 10:09

原始链接:http://qiulyblog.github.io/2019/03/31/[题解]luoguP2495/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。